package com.hy.node;

public class RemoveNode {


    /**
     * 203.移除链表元素
     *
     * 题意：删除链表中等于给定值 val 的所有节点。
     *
     * 示例 1：
     * 输入：head = [1,2,6,3,4,5,6], val = 6
     * 输出：[1,2,3,4,5]
     *
     * 示例 2：
     * 输入：head = [], val = 1
     * 输出：[]
     *
     * 示例 3：
     * 输入：head = [7,7,7,7], val = 7
     * 输出：[]
     *
     */

    static class ListNode {
        // 节点的值
        int val;
        // 下一个节点
        ListNode next;

        public ListNode() {

        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }



        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }

    /**
     * 添加虚节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElements(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        // 因为删除可能涉及到头节点，所以设置dummy节点，统一操作
        // dummy   -1  -> head
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        // cur == head
        ListNode cur = head;
        while (cur != null) {
            // 如果 当前节点的值  等于  要移除的值    前一个节点的下一个节点的值  ==   当前节点下一个的值 （直接更改指针指向）
            if (cur.val == val) {
                pre.next = cur.next;
            } else {
                // 不相等的话   移动指针  将cur赋值给前一个节点
                pre = cur;
            }
            // 无论是否相等， 都将cur后移一位  指向 当前节点
            cur = cur.next;
        }
        return dummy.next;
    }

    /**
     * 不添加虚拟节点方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElement2(ListNode head,int val){
        // 如果当前节点为空  直接返回
        if (head == null){
            return head;
        }
        // 如果当前节点不为空 并且当前节点等于val
        if(head != null && head.val == val){
            head = head.next;
        }
        // 定义  前一个节点  当前节点
        ListNode pre =head;
        ListNode cur = head.next;

        while (cur != null){
            if (cur.val == val){
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        return head;
    }

    /**
     * 不添加虚拟节点and pre Node方式
     * 时间复杂度 O(n)
     * 空间复杂度 O(1)
     * @param head
     * @param val
     * @return
     */
    public static ListNode removeElement3(ListNode head,int val){
        if (head == null){
            return head;
        }
        // 当前节点
        ListNode cur = head;

        while (cur != null){
            while (cur.next != null && cur.next.val == val){
                cur.next = cur.next.next;
            }
            cur = cur.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode listNode5 = new ListNode(5,null);
        ListNode listNode4 = new ListNode(4,listNode5);
        ListNode listNode3 = new ListNode(3,listNode4);
        ListNode listNode2 = new ListNode(2,listNode3);
        ListNode listNode1 = new ListNode(1,listNode2);

        System.out.println("移除元素前："+listNode1.toString());
        int val = 2;
        System.out.println("移除元素后："+removeElements(listNode1, val));
        System.out.println("移除元素后："+removeElement2(listNode1, val));
        System.out.println("移除元素后："+removeElement3(listNode1, val));


    }
}
